#include <stdio.h>

void merge(int *arr, int p, int q, int r) 
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int L[n1];
    int R[n2];
    int i, j, k;

    for(i = 0; i < n1; i++)
        L[i] = arr[p + i];
    
    for(j = 0; j < n2; j++)
        R[j] = arr[q + 1 + j];
    
    i = 0;
    j = 0;
    k = p;
    
    while(i < n1 && j < n2) 
		{
        if(L[i] <= R[j]) 
				{
            arr[k] = L[i];
            i++;
        } 
				else 
				{
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while(i < n1) 
		{
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while(j < n2) 
		{
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int *array, int p, int r) 
{
    if(p < r) 
		{
        int q = (p + r) / 2;
        mergeSort(array, p, q);
        mergeSort(array, q + 1, r);
        merge(array, p, q, r);
    }
}


void main(void)
{
	int num[15]={5,2,4,7,1,3,456,15,555,25,5,6,98,7,15};
	
    for(int i=0;i<15;i++)
	{		
		printf("arraybefore[%d]=%d\r\n",i,num[i]);
	}
	mergeSort(num,0,14);
	for(int i=0;i<15;i++)
	{
		printf("array[%d]=%d\r\n",i,num[i]);
	}

}

